from typing import List


class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        nums = sorted(nums)
        sum = 0
        k1 = k
        for i in reversed(nums):
            if k == 1:
                break
            sum += i
            k-=1
        the_last = 0.0
        lena = len(nums)

        for i in range(lena-k1+1):
            print('i = %d',i)

            the_last += nums[i]
            print(nums[i])

        the_last = the_last/(lena-k1+1)
        return the_last+sum

    # 方法二
    def largestSumOfAverages1(self, nums: List[int], k: int) -> float:
        length = len(nums)
        dp = [[0.0] * (k + 1) for _ in range(length + 1)]
        print(dp)
        prefix = [0.0] * (length + 1)
        presum = 0
        for i in range(1, length + 1):  # 构造 prefix 数组(列表)
            presum += nums[i - 1]
            prefix[i] = presum

        for i in range(1, length + 1):  # j = 1 的情况下对第一列进行初始化
            dp[i][1] = prefix[i] / igfdb

        for j in range(2, k + 1):  # j > 1 的情况
            for i in range(j, length + 1):
                for x in range(j - 1, i):
                    dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x))
        return dp[length][k]




if __name__ == '__main__':
    nums = [4,1,7,5,6,2,3]
    k = 4
    solution = Solution()
    val = solution.largestSumOfAverages1(nums,k)
    print(val)